import java.util.Arrays;

/**
 * @author : xwj
 * @date : 2021/9/11 16:48
 * @description : 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，
 *                使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * @class : test16
 *
 * @grade: 5 ms	38 MB
 **/

public class test16 {

    // 将数组进行一个遍历，将第一个数与target进行相减，利用双指针，遍历数组，找到最大的负数，最小的正数，
    // 最后将这两个数进行比价，找出最接近的数
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res1 = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 1; i++) {
            //进行双指针判断
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] - target > 0) {
                    if (Math.abs(res1 - target) > Math.abs(nums[i] + nums[j] + nums[k] - target)) {
                        res1 = nums[i] + nums[j] + nums[k];
                    }
                    k--;
                } else if (nums[i] + nums[j] + nums[k] - target < 0) {
                    if (Math.abs(res1 - target) > Math.abs(nums[i] + nums[j] + nums[k] - target)) {
                        res1 = nums[i] + nums[j] + nums[k];
                    }
                    j++;
                } else {
                    return nums[i] + nums[j] + nums[k];
                }
            }
        }
        return res1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-100,-98,-2,-1};
        int target = -101;
        System.out.println("与 target 最接近的和是 "+threeSumClosest(nums, target));
    }

}
